「进阶 0x12」双端队列

首先，因为要将它排序为一个不降的序列，所以先给它排个序，然后看哪些段能被分在同一个双端队列里面

先思考一下队列的放置方法，很简单的思路，只有$idx$递增的一段才能放在同一个队列里面对吧

这个时候我们换成的双端队列，多了一个放入的点，所以我们易得任一单谷段皆可以放在一个双端队列里面

我们只需要贪心的找最少的单谷段就行了

#include<bits/stdc++.h>
using namespace std;
#define pii pair< int,int >
#define val first
#define idx second

const int N=2e5+10;

pii a[N];

int main()
{
	freopen( "txt.in","r",stdin );
	int n;
	cin>>n;
	for( int i=1;i<=n;i++ )
		cin>>a[i].val, a[i].idx=i;
	sort( a+1,a+n+1 );
	int lst=INT_MAX, ans=1;
	bool down=true;
	for( int i=1;i<=n; )
	{
		int j=i;
		while( j <= n && a[i].val == a[j].val ) j++;
		int min_idx=a[i].idx, max_idx=a[j-1].idx;
		if( down )
		{
			if( lst > max_idx )
				lst=min_idx;
			else
				lst=max_idx, down^=1;
		}
		else
		{
			if( lst < min_idx )
				lst=max_idx;
			else
				lst=min_idx, down^=1, ans++;
		}
		i=j;
	}
	cout<<ans;
}